using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

namespace HTCollections.Custom
{
    /// <summary>
    /// 自定义哈希表
    /// </summary>
    public sealed class FastHashMap<TKey, TValue> : IEnumerable<KeyValuePair<TKey, TValue>>
        where TKey : IEquatable<TKey>
    {
        public TValue[] Data;
        public int[] Buckets;
        public Slot[] Slots;
        public int Capacity;
        public int BucketSize;
        public int Length;
        public int FreeIndex; //空位索引
        public int LastIndex; //顺序往后的索引
        public EqualityComparer<TKey> Comparer;

        public FastHashMap()
        {
            Capacity = 4;
            BucketSize = 4;
            Data = new TValue[Capacity];
            Buckets = new int[BucketSize];
            Slots = new Slot[Capacity];
            Length = 0;
            FreeIndex = -1;
            LastIndex = 0;
            Comparer = EqualityComparer<TKey>.Default;
        }

        public FastHashMap(int capacity)
        {
            Capacity = capacity;
            BucketSize = capacity;
            Data = new TValue[Capacity];
            Buckets = new int[BucketSize];
            Slots = new Slot[Capacity];
            Length = 0;
            FreeIndex = -1;
            LastIndex = 0;
            Comparer = EqualityComparer<TKey>.Default;
        }

        public FastHashMap(int capacity, int bucketSize)
        {
            Capacity = capacity;
            BucketSize = bucketSize;
            Data = new TValue[Capacity];
            Buckets = new int[BucketSize];
            Slots = new Slot[Capacity];
            Length = 0;
            FreeIndex = -1;
            LastIndex = 0;
            Comparer = EqualityComparer<TKey>.Default;
        }

        public FastHashMap(FastHashMap<TKey, TValue> hashMap)
        {
            Capacity = hashMap.Capacity;
            BucketSize = hashMap.BucketSize;
            Data = new TValue[Capacity];
            Buckets = new int[BucketSize];
            Slots = new Slot[Capacity];
            Length = hashMap.Length;
            FreeIndex = hashMap.FreeIndex;
            LastIndex = hashMap.LastIndex;
            Comparer = hashMap.Comparer;
            Array.Copy(hashMap.Data, 0, Data, 0, Length);
            Array.Copy(hashMap.Buckets, 0, Buckets, 0, BucketSize);
            Array.Copy(hashMap.Slots, 0, Slots, 0, Length);
        }

        public TValue this[TKey key]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                int bucketIndex = GetBucketIndex(key);
                int index = Buckets[bucketIndex] - 1;
                while (index >= 0)
                {
                    var slot = Slots[index];
                    if (Comparer.Equals(slot.Key, key))
                    {
                        return Data[index];
                    }

                    index = slot.NextIndexPlusOne - 1;
                }

                throw new KeyNotFoundException($"get value error! {key} not found in hash map");
            }
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            set
            {
                int bucketIndex = GetBucketIndex(key);
                int index = Buckets[bucketIndex] - 1;
                while (index >= 0)
                {
                    var slot = Slots[index];
                    if (Comparer.Equals(slot.Key, key))
                    {
                        Data[index] = value;
                        return;
                    }

                    index = slot.NextIndexPlusOne - 1;
                }

                throw new KeyNotFoundException($"set value error! {key} not found in hash map");
            }
        }

        /// <summary>
        /// 扩容
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Expend()
        {
            int newCapacity = ArrayUtil.GetCapacity(Capacity);
            int newBucketSize = ArrayUtil.GetCapacity(BucketSize);
            FastHashMap<TKey, TValue> newHashMap = new FastHashMap<TKey, TValue>(newCapacity, newBucketSize);
            foreach (var item in this)
                newHashMap.Add(item.Key, item.Value);
            Capacity = newHashMap.Capacity;
            BucketSize = newHashMap.BucketSize;
            Data = newHashMap.Data;
            Buckets = newHashMap.Buckets;
            Slots = newHashMap.Slots;
            FreeIndex = -1;
            LastIndex = newHashMap.Length;
        }

        /// <summary>
        /// 扩容
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Resize(int newCapacity, int newBucketSize)
        {
            if (Capacity == newCapacity && BucketSize == newBucketSize) return;
            FastHashMap<TKey, TValue> newHashMap = new FastHashMap<TKey, TValue>(newCapacity, newBucketSize);
            foreach (var item in this)
                newHashMap.Add(item.Key, item.Value);
            Capacity = newHashMap.Capacity;
            BucketSize = newHashMap.BucketSize;
            Data = newHashMap.Data;
            Buckets = newHashMap.Buckets;
            Slots = newHashMap.Slots;
            FreeIndex = -1;
            LastIndex = newHashMap.Length;
        }

        /// <summary>
        /// 添加键值对
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Add(TKey key, TValue value)
        {
            int bucketIndex = GetBucketIndex(key);
            int index = Buckets[bucketIndex] - 1;
            while (index >= 0)
            {
                var slot = Slots[index];
                if (Comparer.Equals(slot.Key, key))
                    return false; //已有key
                index = slot.NextIndexPlusOne - 1;
            }

            if (FreeIndex >= 0)
            {
                index = FreeIndex;
                FreeIndex = Slots[index].NextIndexPlusOne - 1;
            }
            else
            {
                if (LastIndex == Capacity)
                {
                    Expend();
                    bucketIndex = GetBucketIndex(key);
                }

                index = LastIndex;
                LastIndex++;
            }

            var newSlot = new Slot()
            {
                Key = key,
                NextIndexPlusOne = Buckets[bucketIndex],
            };
            Slots[index] = newSlot;
            Data[index] = value;
            Buckets[bucketIndex] = index + 1; //IndexPlusOne
            Length++;

            //扩容
            if (1f * Length / BucketSize >= 0.7f)
                Expend();
            return true;
        }

        /// <summary>
        /// 添加键值对集合
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void AddRange(FastHashMap<TKey, TValue> other)
        {
            if (other.Length == 0) return;
            int newSize = Length + other.Length;
            if (1f * newSize / BucketSize >= 0.7f)
                Resize(ArrayUtil.GetCapacity(Capacity), ArrayUtil.GetCapacity(BucketSize));
            foreach (var item in other)
                Add(item.Key, item.Value);
        }

        /// <summary>
        /// 移除键（返回值）
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Remove(TKey key, out TValue value)
        {
            int bucketIndex = GetBucketIndex(key);
            int index = Buckets[bucketIndex] - 1;
            int prevIndex = -1;
            while (index >= 0)
            {
                var slot = Slots[index];
                if (Comparer.Equals(slot.Key, key))
                {
                    if (prevIndex >= 0) //非头节点
                    {
                        if (slot.NextIndexPlusOne > 0) //有子节点
                            Slots[prevIndex].NextIndexPlusOne = slot.NextIndexPlusOne;
                        else //无子节点
                            Slots[prevIndex].NextIndexPlusOne = 0;
                    }
                    else //头节点
                        Buckets[bucketIndex] = 0;

                    value = Data[index];
                    Data[index] = default;
                    Slots[index] = new Slot()
                    {
                        Key = default,
                        NextIndexPlusOne = FreeIndex + 1, //使用指针记录空格
                    };
                    Length--;
                    if (Length == 0)
                    {
                        FreeIndex = -1;
                        LastIndex = 0;
                    }
                    else
                        FreeIndex = index;

                    return true;
                }

                prevIndex = index;
                index = slot.NextIndexPlusOne - 1;
            }

            value = default;
            return false;
        }

        /// <summary>
        /// 移除键
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Remove(TKey key)
        {
            int bucketIndex = GetBucketIndex(key);
            int index = Buckets[bucketIndex] - 1;
            int prevIndex = -1;
            while (index >= 0)
            {
                var slot = Slots[index];
                if (Comparer.Equals(slot.Key, key))
                {
                    if (prevIndex >= 0) //非头节点
                    {
                        if (slot.NextIndexPlusOne > 0) //有子节点
                            Slots[prevIndex].NextIndexPlusOne = slot.NextIndexPlusOne;
                        else //无子节点
                            Slots[prevIndex].NextIndexPlusOne = 0;
                    }
                    else //头节点
                        Buckets[bucketIndex] = 0;

                    Data[index] = default;
                    Slots[index] = new Slot()
                    {
                        Key = default,
                        NextIndexPlusOne = FreeIndex + 1, //使用指针记录空格
                    };
                    Length--;
                    if (Length == 0)
                    {
                        FreeIndex = -1;
                        LastIndex = 0;
                    }
                    else
                        FreeIndex = index;

                    return true;
                }

                prevIndex = index;
                index = slot.NextIndexPlusOne - 1;
            }

            return false;
        }

        /// <summary>
        /// 尝试通过键获取值
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool TryGetValue(TKey key, out TValue value)
        {
            int bucketIndex = GetBucketIndex(key);
            int index = Buckets[bucketIndex] - 1;
            while (index >= 0)
            {
                var slot = Slots[index];
                if (Comparer.Equals(slot.Key, key))
                {
                    value = Data[index];
                    return true;
                }

                index = slot.NextIndexPlusOne - 1;
            }

            value = default;
            return false;
        }

        /// <summary>
        /// 清空哈希表
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Clear()
        {
            if (Length == 0) return;
            Array.Clear(Data, 0, Capacity);
            Array.Clear(Buckets, 0, BucketSize);
            Array.Clear(Slots, 0, Capacity);
            Length = 0;
            FreeIndex = -1;
            LastIndex = 0;
        }

        /// <summary>
        /// 检测是否包含指定键
        /// </summary>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool ContainsKey(TKey key)
        {
            int bucketIndex = GetBucketIndex(key);
            int index = Buckets[bucketIndex] - 1;
            while (index >= 0)
            {
                var slot = Slots[index];
                if (Comparer.Equals(slot.Key, key))
                    return true;
                index = slot.NextIndexPlusOne - 1;
            }

            return false;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        int GetBucketIndex(TKey key)
        {
            int hashCode = key.GetHashCode();
            return (hashCode > 0 ? hashCode : -hashCode) % BucketSize;
        }

        public struct Slot
        {
            public TKey Key;
            public int NextIndexPlusOne;
        }

        IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
        {
            return GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }

        public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
        {
            FastHashMap<TKey, TValue> mHashMap;
            int mIndex;
            int mCurrentIndex; //当前索引
            int mBucketIndex; //在bucket中的索引
            int mNodeIndex; //在链表中的索引
            bool mIsLeaf; //是否为链表的叶子节点

            public KeyValuePair<TKey, TValue> Current
            {
                [MethodImpl(MethodImplOptions.AggressiveInlining)]
                get
                {
                    TKey key = mHashMap.Slots[mCurrentIndex].Key;
                    TValue value = mHashMap.Data[mCurrentIndex];
                    return new KeyValuePair<TKey, TValue>(key, value);
                }
            }

            object IEnumerator.Current => Current;

            public Enumerator(FastHashMap<TKey, TValue> hashMap)
            {
                mHashMap = hashMap;
                mIndex = -1;
                mCurrentIndex = -1;
                mBucketIndex = -1;
                mNodeIndex = -1;
                mIsLeaf = true;
            }

            public bool MoveNext()
            {
                mIndex++;
                if (mIndex >= mHashMap.Length)
                    return false;
                mNodeIndex = mIsLeaf ? 0 : mNodeIndex + 1;
                for (int i = mBucketIndex + (mIsLeaf ? 1 : 0), bucketSize = mHashMap.BucketSize; i < bucketSize; i++)
                {
                    mCurrentIndex = mHashMap.Buckets[i] - 1;
                    if (mCurrentIndex < 0) continue;
                    for (int j = 0; j < mNodeIndex; j++)
                    {
                        mCurrentIndex = mHashMap.Slots[mCurrentIndex].NextIndexPlusOne - 1;
                        if (mCurrentIndex < 0) break;
                    }

                    if (mCurrentIndex < 0)
                    {
                        mNodeIndex = 0;
                        continue;
                    }

                    mBucketIndex = i;
                    mIsLeaf = mHashMap.Slots[mCurrentIndex].NextIndexPlusOne == 0;
                    break;
                }

                return true;
            }

            public void Reset()
            {
                mIndex = -1;
                mCurrentIndex = -1;
                mBucketIndex = -1;
                mNodeIndex = -1;
                mIsLeaf = true;
            }

            public void Dispose()
            {
            }
        }
    }
}